#include "node.h"
#include "context.h"
#include "error.h"

Node::Node(const unsigned n, SimulationContext *c, double b, double l) :
	number(n), context(c), bw(b), lat(l) {
}

Node::Node() {
	throw GeneralException();
}

Node::Node(const Node &rhs) :
	number(rhs.number), context(rhs.context), bw(rhs.bw), lat(rhs.lat) {
}

Node & Node::operator=(const Node &rhs) {
	return *(new (this) Node(rhs));
}

void Node::SetNumber(const unsigned n) {
	number = n;
}

unsigned Node::GetNumber() const {
	return number;
}

void Node::SetLatency(const double l) {
	lat = l;
}

double Node::GetLatency() const {
	return lat;
}

void Node::SetBW(const double b) {
	bw = b;
}

double Node::GetBW() const {
	return bw;
}

Node::~Node() {
}

// Implement these functions to post an event to the event queue in the event simulator
// so that the corresponding node can receive the ROUTING_MESSAGE_ARRIVAL event at the proper time
void Node::SendToNeighbors(RoutingMessage *m) {
	deque<Node*> *neighborNodes = GetNeighbors();
	deque<Node*>::iterator nodeIT;

	for (nodeIT = neighborNodes->begin(); nodeIT != neighborNodes->end(); nodeIT++) {
		SendToNeighbor(*nodeIT, m);
	}

	/*
	 // This code prints out what is being sent by each node and where it is sending it
	 deque<Node*> *neighborList = GetNeighbors();
	 deque<Node*>::iterator neighborIT;

	 map<unsigned int, double>::iterator mapIT;

	 cout << "Current Node ID (outer map key) : " << this->GetNumber() << " => " << "(outer map value):" << endl;
	 for (mapIT = m->m_mapMessage.begin(); mapIT != m->m_mapMessage.end(); mapIT++)
	 {
	 cout << "\t" << (*mapIT).first << " => " << (*mapIT).second << endl;
	 }

	 for (neighborIT = (*neighborList).begin(); neighborIT != (*neighborList).end(); neighborIT++)
	 {
	 // send the toSend map to each of these neighbors ..
	 cout << "Sending to Neighbor " << (**neighborIT).GetNumber() << endl;
	 }
	 cout << "------------------------------------------------------------" << endl << endl;
	 */

}

void Node::SendToNeighbor(const Node *n, const RoutingMessage *m) {
	deque<Link*> *neighborLinks = context->GetOutgoingLinks(n);
	deque<Link*>::iterator linkIT;
	Link lnMatch;

	for (linkIT = neighborLinks->begin(); linkIT != neighborLinks->end(); linkIT++) {
		// find the matching link
		// here we compare the source of the link instead of the destination because at this point Node n is a neighbor to the original node
		// so the link from the neighbor Node n is pointing to the original node; this will always be equivalent unless for some reason
		// the link from A => B has a different latency than the link from B => A
		if ((**linkIT).GetSrc() == n->GetNumber()) {
			lnMatch = (**linkIT);
			break;
		}
	}

	//cout << "cur time + latency = " << context->GetTime() + lnMatch.GetLatency() << endl;
	Event *e = new Event(context->GetTime() + lnMatch.GetLatency(), // latency time of event
			ROUTING_MESSAGE_ARRIVAL, // type of event
			(void*) n, // pointer to node object which will handle the event
			(void*) m); // data, pointer to the routing message to send	

	// post the event; this simulates actually sending it
	context->PostEvent(e);
}

deque<Node*> *Node::GetNeighbors() {
	return context->GetNeighbors(this);
}

void Node::SetTimeOut(const double timefromnow) {
	context->TimeOut(this, timefromnow);
}

bool Node::Matches(const Node &rhs) const {
	return number == rhs.number;
}

#if defined(GENERIC)
void Node::LinkHasBeenUpdated(const Link *l)
{
	cerr << *this << " got a link update: "<<*l<<endl;
	//Do Something generic:
	SendToNeighbors(new RoutingMessage);
}

void Node::ProcessIncomingRoutingMessage(const RoutingMessage *m)
{
	cerr << *this << " got a routing messagee: "<<*m<<" Ignored "<<endl;
}

void Node::TimeOut()
{
	cerr << *this << " got a timeout: ignored"<<endl;
}

Node *Node::GetNextHop(const Node *destination) const
{
	return 0;
}

Table *Node::GetRoutingTable() const
{
	return new Table;
}

ostream & Node::Print(ostream &os) const
{
	os << "Node(number="<<number<<", lat="<<lat<<", bw="<<bw<<")";
	return os;
}

#endif

/////////////////////////////////////////////////////////////
// 
// Link State
// 
/////////////////////////////////////////////////////////////

#if defined(LINKSTATE)

void Node::LinkHasBeenUpdated(const Link *l)
{
	//cerr << *this<<": Link Update: "<<*l<<endl;
    deque<Node*> * nodeList = context->GetNodeList();
	UpdateAllRoutingTable(*nodeList);
}

void Node::ProcessIncomingRoutingMessage(const RoutingMessage *m)
{
	// cerr << *this << " Routing Message: "<<*m;
	cout << "======== message ========" << endl;
    deque<Node*> * nodeList = context->GetNodeList();
	UpdateAllRoutingTable(*nodeList);
}

void Node::PrintForwardingTable()
{
  cout << "Not yet implemented for Link State" << endl;
}

void Node::TimeOut()
{
	cerr << *this << " got a timeout: ignored"<<endl;
}

Node *Node::GetNextHop(const Node *destination)
{
	// WRITE
	// deque<Link *> path = m_RoutingTable.GetShortestPath(destination -> GetNumber());
	// deque<Link *>::iterator first = path.begin();

	// Node nextNode;
	// nextNode.SetNumber((*first)->GetDest());
	// return context->FindMatchingNode(&nextNode);
	return NULL;
}

Table * Node::GetRoutingTable()
{
	// WRITE
	return &m_RoutingTable;
}

ostream & Node::Print(ostream &os) const
{
	os << "Node(number="<<number<<", lat="<<lat<<", bw="<<bw<<")";
	return os;
}

/* new added funcions*/
void Node::ConstructRoutingTable(Node *curNode, deque<Node*> *nodeList)
{
	cout << "==== Node::ConstructRoutingTable" << endl;
	// PrintNodeList(*nodeList);
	UpdateAllRoutingTable(*nodeList);
}

bool Node::IncludeNode(unsigned num, deque<Node*> nodeList)
{
	for (deque<Node*>::iterator i = nodeList.begin(); i != nodeList.end(); ++i)
	{
		if ((*i)->GetNumber() == num)
		{
			return true;
		}
	}

	return false;
}

void Node::UpdateAllRoutingTable(deque<Node*> nodeList)
{
	m_RoutingTable.clear();
	deque<Node *> qLeft;
	deque<Node *>::iterator it;
	
	for(it = nodeList.begin(); it != nodeList.end(); ++it)
	{
		if((*it)->GetNumber() == number)
		{
			break;
		}
	}
	
	Node * selfNode = (*it);
	qLeft.push_back(selfNode);
	// delete the node itself from the all node list
	nodeList.erase(it);
	
	while (!nodeList.empty()){
		// cout << "for the node:" << number;
		// PrintNodeList(nodeList);

		deque<Node *>::iterator itl;

		Link * minLink = NULL;

		for (itl = qLeft.begin(); itl != qLeft.end(); itl ++)
		{
			deque<Link*> *neighborLinks = context->GetOutgoingLinks(*itl);
			for (std::deque<Link*>::iterator i = (*neighborLinks).begin(); i != (*neighborLinks).end(); ++i)
			{
				unsigned dest = (*i)->GetDest();
				if (IncludeNode(dest, qLeft))
				{
					// do nothing
				} else if (!minLink || (*i)->GetLatency() < minLink->GetLatency())
				{
					minLink = (*i);
				}
			}
		}
		
		unsigned minSrc = minLink->GetSrc();
		unsigned minDest = minLink->GetDest();
 		// cout << "--the minSrc is:"  << minSrc << endl;
 		// cout << "--the minDest is:" << minDest << endl;

		// delete the new found node.
		deque<Node*>::iterator iDest = nodeList.begin();
		while((*iDest)->GetNumber() != minDest && iDest != nodeList.end())
			iDest ++;
		Node * pDestNode = (*iDest);
		nodeList.erase(iDest);
		qLeft.push_back(pDestNode);

		// create the minimal path from self to the dest nodes and store it into map.
		deque<Link *> shortestPath;
		if (minSrc != number)
		{
//			cout << "----the src is self:" << number << endl;
			deque<Link *> path = m_RoutingTable.GetShortestPath(minSrc);
			for (std::deque<Link *>::iterator i = path.begin(); i != path.end(); ++i)
			{
				shortestPath.push_back(*i);
			}
		}
		shortestPath.push_back(minLink);
		m_RoutingTable.SetShortestPath(minDest, shortestPath);
		PrintShortestPath(minDest);
	}

	this->PrintRoutingTable();	
}


void Node::PrintNodeList(deque<Node *> nodeList)
{
	std::deque<Node *>::iterator i = nodeList.begin();
	for (; i != nodeList.end(); ++i)
	{
		cout << (*i)->GetNumber() << " -> ";
	}
	//cout << (*(i+1))->GetNumber() << ";" << endl;
	cout << endl;
}

void Node::PrintLinkList(deque<Link *> nodeList)
{
	std::deque<Link *>::iterator i = nodeList.begin();
	for (; i != nodeList.end(); ++i)
	{
		cout << "(" << (*i)->GetSrc() << " -> " << (*i)->GetDest() << ")" << ";";
	}

	cout << endl;
}

void Node::PrintShortestPath(unsigned dest)
{
//	cout << "the shortest path from:" << dest << endl;
//	PrintLinkList(m_rTable.GetShortestPath(dest));
}


void Node::PrintRoutingTable()
{
  m_RoutingTable.Print(number);
}

#endif

	/////////////////////////////////////////////////////////////
	// 
	// Distance Vector
	// 
	/////////////////////////////////////////////////////////////

#if defined(DISTANCEVECTOR)

void Node::LinkHasBeenUpdated(const Link *l)
{
  m_RoutingTable.SetRoutingValue(l->GetSrc(), l->GetDest(), l->GetLatency());
  bool blnMapChanged = RecalculateLocalDistanceVector();

  if (true == blnMapChanged)
  {
    RoutingMessage *rMessage = GetVectorInRoutingMessage();
    SendToNeighbors(rMessage);
  }
}

void Node::ProcessIncomingRoutingMessage(const RoutingMessage *m)
{
  //cout << "Node " << this->GetNumber() << " just received an update from " << m->m_uintSource << ":" << endl;
  bool blnDistanceVectorChanged = false;
  // overwrite the local distance vector with the received distance vector in the routing message m
  // For example if node 4 the message to node 2, then the message contains D4 and this node (node
  // 2), needs to replace its copy of D4 with the received copy
  UpdateNodeRoutingTable(m);

  // now update the local node's distance vector using the Bellman-Ford equation.  Continuing the
  // the example above, node 2 needs to recalculate D2
  //blnDistanceVectorChanged = RecalculateLocalDistanceVector(m);
  blnDistanceVectorChanged = RecalculateLocalDistanceVector();

  // if the local node distance vector changed, send it to all its neighbors.  Continuing with the
  // example, if D2 changed, send it to all of node 2's neighbors
  if (true == blnDistanceVectorChanged)
  {
    //cout << "The routing table changed! This is Node " << this->GetNumber() << "'s new routing table:" << endl;
    //PrintRoutingTable();
    //cout << "Sending updates to all of Node " << this->GetNumber() << "'s neighbors" << endl;
    // send distance vector to all neighbors
    RoutingMessage *rMessage = GetVectorInRoutingMessage();
    //cout << "this should match what was inserted in the table above" << endl;
    //rMessage->PrintRoutingMessage();
    SendToNeighbors(rMessage);    
  }
}

double Node::GetLinkCost(unsigned int uintSource, unsigned int uintDest)
{
	deque<Link*> *neighborLinks = context->GetOutgoingLinks(this);
	deque<Link*>::iterator linkIT;

	double linkCost = -1;

	for (linkIT = (*neighborLinks).begin(); linkIT != (*neighborLinks).end(); linkIT++)
	{
		if (uintSource == (**linkIT).GetSrc() && uintDest == (**linkIT).GetDest())
		{
			linkCost = (**linkIT).GetLatency();
			break;
		}
	}

	// if this link could not be found for some reason, just return the value found in the table
	if (linkCost == -1)
	{
		linkCost = m_RoutingTable.GetRoutingCost(uintSource, uintDest);
	}

	return linkCost;
}

bool Node::RecalculateLocalDistanceVector()
{
  // at this point the received distance vector should already be updated in the routing table
  bool blnTableChanged = false;
  //unsigned int fromNodeID = m->m_uintSource;
  unsigned int localNodeID = this->GetNumber();
  map<unsigned int, map<unsigned int, double> >::iterator localNodeDV = m_RoutingTable.Find(localNodeID);
  map<unsigned int, double>::iterator localInnerMapIT;
  deque<Node*> *neighborList = GetNeighbors();
  deque<Node*>::iterator neighborListIT;


  // loops through the distance vector for the local node
  for (localInnerMapIT = (*localNodeDV).second.begin(); localInnerMapIT != (*localNodeDV).second.end(); localInnerMapIT++)
  {
    double *allCosts = (double*)malloc( sizeof(double) * (*neighborList).size() + 1);
    map<double, Node*> costToNodeID;	// use this to keep track of the cost to Node ID
    size_t index = 0;
    //cout << "local node: " << this->GetNumber() << " :checking " << (*localInnerMapIT).first << " => " << endl;
    if ((*localInnerMapIT).first != localNodeID)	// the routing cost from a node to itself will always be 0 so just skip this case
    {
      //cout << "\t" << localNodeID << " => " << (*localInnerMapIT).first << endl;
      double curTableValue = m_RoutingTable.GetRoutingCost(localNodeID, (*localInnerMapIT).first);
      // now loops through all the neighbors to the local node
      for (neighborListIT = (*neighborList).begin(); neighborListIT != (*neighborList).end(); neighborListIT++)
      {
	double tempCostToNeighbor = GetLinkCost(localNodeID, (**neighborListIT).GetNumber());
	double distFromNeighborToDest = m_RoutingTable.GetRoutingCost((**neighborListIT).GetNumber(), (*localInnerMapIT).first);
	if (tempCostToNeighbor == -1) return false;
	if (distFromNeighborToDest == INFINITY) distFromNeighborToDest = 0;
	allCosts[index] = tempCostToNeighbor + distFromNeighborToDest;
	// keep track of which cost belongs with which Node ID so we can update the forwarding table appropriately
	costToNodeID.insert( pair<double, Node*>(allCosts[index], *neighborListIT) );
	index++;
      }
      double minFromList = *min_element(allCosts, allCosts+(*neighborList).size());
      if (minFromList != curTableValue)
      {
	//cout << "New min cost to destination = " << minFromList << endl;
	m_RoutingTable.SetRoutingValue(localNodeID, (*localInnerMapIT).first, minFromList);
	blnTableChanged = true;
      }
      // now find the node associated with this min cost
      map<double, Node*>::iterator costIT = costToNodeID.find(minFromList);
      if (costIT != costToNodeID.end())
      {
	// then insert this neighbor as the next next hop node for destination specified by the localInnerMapIT node iterator
	UpdateForwardingTable((*localInnerMapIT).first, (*costIT).second);
      }
      delete allCosts;
    }
  }
  return blnTableChanged;
}

void Node::UpdateForwardingTable(unsigned int nodeID, Node *nextHopNode)
{
  map<unsigned int, Node*>::iterator costIT = m_ForwardingTable.find(nodeID);

  if (costIT != m_ForwardingTable.end())
  {
    (*costIT).second = nextHopNode;
  }else{
    cout << "Unable to find Node " << nodeID << " in forwarding table (perhaps you should just insert it instead of displaying this message" << endl;
  }
}

void Node::UpdateNodeRoutingTable(const RoutingMessage *m)
{
	// Get the node ID that the message came from
	unsigned int fromNodeID = m->m_uintSource;

	// find the entry for the source node in this node's routing table
	map<unsigned int, map<unsigned int, double> >::iterator outerMapIT;
	outerMapIT = m_RoutingTable.Find(fromNodeID);

  if (outerMapIT == m_RoutingTable.End())
  {
    cout << "Couldn't find entry in table!!" << endl;
  }else{
    m_RoutingTable.SetInnerMapValue(outerMapIT, m->m_mapMessage);
    //cout << "Node " << this->GetNumber() << "'s new routing table:" << endl;
    //this->PrintRoutingTable();
  }
}

void Node::ConstructRoutingTable(Node *curNode, deque<Node*> *nodeList)
{
  map<unsigned int, double> tempInnerMap;
  map<unsigned int, map<unsigned int, double> > tempOuterMap;
  pair<map<unsigned int, double>::iterator,bool> retInner;
  pair<map<unsigned int, map<unsigned int, double> >::iterator,bool> retOuter;
  deque<Node*> *neighborList = GetNeighbors();
  deque<Node*>::iterator outerNodeIT;
  deque<Node*>::iterator innerNodeIT;
  bool blnFound = false;

	// first insert the current node into the table
	// this inserts the node ID and latency value of the current node into an inner map
	retInner = tempInnerMap.insert( pair<unsigned int, double>((*curNode).GetNumber(), 0) );
	if (false == retInner.second)
	{
		//cout << "Node " << (*curNode).GetNumber() << " already exists with a latency of " << "0" << "!" << endl;
	}

	// now insert the the remaining nodeID/latencies from the neighbor list to the inner map that will be
	// keyed to the current node outer map (doesn't make much sense to me either)
	for (innerNodeIT = (*nodeList).begin(); innerNodeIT != (*nodeList).end(); innerNodeIT++)
	{
		/* if (node in nodeList is also in neighborList (the node is a neighbor))
		 then insert the node in the map with the node's latency
		 else
		 insert the node in the map with infinite latency
		 */
		for (outerNodeIT = (*neighborList).begin(); outerNodeIT != (*neighborList).end(); outerNodeIT++)
		{
			if ((**innerNodeIT).GetNumber() == (**outerNodeIT).GetNumber())
			{
				blnFound = true; // the node in the nodeList is a neighbor of this node
				break;
			}
		}

		if (true == blnFound) // the node is a neighbor
		{
			retInner = tempInnerMap.insert( pair<unsigned int, double>((**innerNodeIT).GetNumber(), (**innerNodeIT).GetLatency()) );
			blnFound = false; // re-initialize this flag
		} else { // the node is not a neighbor, insert with infinite latency
			retInner = tempInnerMap.insert( pair<unsigned int, double>((**innerNodeIT).GetNumber(), INFINITY) );
		}

		if (false == retInner.second)
		{
			//cout << "1 - Trying to insert duplicate key/value into inner map!: " << (**innerNodeIT).GetNumber() << " => " << DBL_MAX << endl;
		}
	}

	// now insert this inner value into the outer map, where the key value of the outer map is the current node
	retOuter = tempOuterMap.insert( pair<unsigned int, map<unsigned int, double> >((*curNode).GetNumber(), tempInnerMap) );
	if (false == retOuter.second)
	{
		//cout << "Node " << (*curNode).GetNumber() << " already exists in the outer map " << endl;
	}

	// the table should now have 1 outer entry; that is, the current node as the key and its value should
	// be current node and all the nodes in the nodeList mapped to their respective link costs

	// now, go through each node in the neighborList... add the current node and neighbors to an inner map and add that inner map
	// to each node outer map (each node should only maintain its own distance vector and the distance vector of its neighbors)
	//for (outerNodeIT = (*nodeList).begin(); outerNodeIT != (*nodeList).end(); outerNodeIT++)
	for (outerNodeIT = (*neighborList).begin(); outerNodeIT != (*neighborList).end(); outerNodeIT++)

	{
		tempInnerMap.clear();
		// if the outer key value is not the current node (its at this point, that case was handled above), then
		// the initial values in the table for distances should be infinity (signified by DBL_MAX)
		// add the current node first
		retInner = tempInnerMap.insert( pair<unsigned int, double>((*curNode).GetNumber(), INFINITY) );
		if (false == retInner.second)
		{
			//cout << "2 - Trying to insert duplicate key/value into inner map!: " << (**outerNodeIT).GetNumber() << " => " << DBL_MAX << endl;
		}

		// now loop through the neighbors
		for (innerNodeIT = (*nodeList).begin(); innerNodeIT != (*nodeList).end(); innerNodeIT++)
		{
			retInner = tempInnerMap.insert( pair<unsigned int, double>((**innerNodeIT).GetNumber(), INFINITY) );
			if (false == retInner.second)
			{
				//cout << "Problem 3!" << endl;
			}
		}

		// and finally add this inner map to the current outer map key
		retOuter = tempOuterMap.insert( pair<unsigned int, map<unsigned int, double> >((**outerNodeIT).GetNumber(), tempInnerMap) );
		if (false == retOuter.second)
		{
			//cout << "Problem 4!" << endl;
		}
  }

	// copy the tempOutMap to the Table member variable
  m_RoutingTable = Table(tempOuterMap, (*curNode).GetNumber());

  // Just initialize each node's forwarding table here
  InitializeForwardingTable(nodeList);

  //PrintForwardingTable();

  //(*curNode).PrintRoutingTable();
}

void Node::InitializeForwardingTable(deque<Node*> *nodeList)
{
  deque<Node*>::iterator nodeIT;

  for (nodeIT = (*nodeList).begin(); nodeIT != (*nodeList).end(); nodeIT++)
  {
    if ((**nodeIT).GetNumber() == this->GetNumber())
    {
      m_ForwardingTable.insert( pair<unsigned int, Node*>(this->GetNumber(), this) );
    }else{
      m_ForwardingTable.insert( pair<unsigned int, Node*>((**nodeIT).GetNumber(), NULL) );
    }
  }
}

//void Node::SendDistanceVectorToNeighbors(deque<Node*> *neighborList)
RoutingMessage *Node::GetVectorInRoutingMessage()
{
	RoutingMessage *rMessage = new RoutingMessage(m_RoutingTable.GetRoutingValueVector((*this).GetNumber()),
			(*this).GetNumber());
	//rMessage->m_mapMessage = m_RoutingTable.GetRoutingValueVector((*this).GetNumber());

	return rMessage;
}

void Node::PrintForwardingTable()
{
  map<unsigned int, Node*>::iterator forwardIT;

  cout << "----------------------------------------------------------------------" << endl;
  cout << "Node " << this->GetNumber() << " Forwarding Table (in the format, Final Destination => Next Hop):" << endl;

  for (forwardIT = m_ForwardingTable.begin(); forwardIT != m_ForwardingTable.end(); forwardIT++)
  {
    cout << "\t" << (*forwardIT).first << " => ";
    if ((*forwardIT).second == NULL)
    {
      cout << "NULL";
    }else{
      cout << (*forwardIT).second->GetNumber();
    }
    cout << endl;
  }
  cout << "----------------------------------------------------------------------" << endl << endl;
}

void Node::PrintRoutingTable()
{
  m_RoutingTable.Print((*this).GetNumber());
  //cout << m_RoutingTable << endl;
}

void Node::TimeOut()
{
  cerr << *this << " got a timeout: ignored"<<endl;
}

Node *Node::GetNextHop(const Node *destination)
{
  map<unsigned int, Node*>::iterator nextHopIT = m_ForwardingTable.find(destination->GetNumber());

  if (nextHopIT != m_ForwardingTable.end())
  {
    return (*nextHopIT).second;
  }else{
    return NULL;
  }
}

Table *Node::GetRoutingTable()
{
	return &m_RoutingTable;
}

ostream & Node::Print(ostream &os) const
{
	os << "Node(number="<<number<<", lat="<<lat<<", bw="<<bw;
	return os;
}

#endif // defined(DISTANCEVECTOR)

